package org.usmile.algorithms.leetcode.simple;

/**
 * 459. 重复的子字符串
 *
 * 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
 *
 * 示例 1:
 *
 * 输入: s = "abab"
 * 输出: true
 * 解释: 可由子串 "ab" 重复两次构成。
 * 示例 2:
 *
 * 输入: s = "aba"
 * 输出: false
 * 示例 3:
 *
 * 输入: s = "abcabcabcabc"
 * 输出: true
 * 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
 *
 * 提示：
 *
 * 1 <= s.length <= 104
 * s 由小写英文字母组成
 */
public class _0459 {
    public static void main(String[] args) {
        new _0459_Solution().repeatedSubstringPattern("aabaaba");
    }
}

class _0459_Solution {
    public boolean repeatedSubstringPattern(String s) {
        if (s.length() <= 1) {
            return false;
        }

        int maxSubLen = s.length() / 2;
        for (int len = 1; len <= maxSubLen; len++) {
            if (s.length() % len != 0) {
                continue;
            }
            int i = 0;
            int j = len;
            while (j < s.length()) {
                if (s.charAt(i) != s.charAt(j)) {
                    break;
                }
                i++;
                j++;
            }

            if (j == s.length()) {
                return true;
            }
        }

        return false;
    }
}

class _0459_Solution1 {
    public boolean repeatedSubstringPattern(String s) {
        if (s.length() <= 1) {
            return false;
        }

        int maxSubLen = s.length() / 2;
        for (int len = 1; len <= maxSubLen; len++) {
            String subString = s.substring(0, len);
            loop:
            for (int start = len; start <= s.length() - len; start += len) {
                int i = 0;
                for (; i < len; i++) {
                    if (subString.charAt(i) != s.charAt(start + i)) {
                        break loop;
                    }
                }

                if (start + i == s.length()) {
                    return true;
                }
            }
        }

        return false;
    }
}
